package demo1;
 class ListNode {
       int val;
       ListNode next;
       ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
class Solution1 {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }
      /*   //(1)在此处设计时，是将头结点包含在内的设计思想
      ListNode cur =  head;
        ListNode prev = head;
        while (cur!=null){ //开始遍历所有的节点
            if(cur.val ==val){
                //需要先进行判断，此节点是否为头节点
                if(cur ==head){
                    head = head.next;
                    cur = cur.next;
                    prev = prev.next;
                }
                //如果不为头结点
                else {
                    //则删除所有对此节点的引用
                    cur =cur.next;
                    prev.next = cur;
                }
            }
//当没有遇到指定关键字时
    else{
            prev = cur;
            cur = cur.next;
    }

    }*/
        //(2)将头结点与链表中其他节点分开处理的思想
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur!=null){
            if(cur.val ==val){
                prev.next =    cur.next;
                cur = cur.next;
            }else {
                //如果此节点不为指定的关键字
                prev = cur;
                cur = cur.next;
            }
        }
       if(head.val ==val){
           head = head.next;
       }

        return head;


    }
}
//第二道题：反转一个单链表

class Solution2 {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        //逆转链表
    /*    //  思想1：首节点不动，将首节点后的节点依次插入到首节点之前
        ListNode cur = head;
        ListNode curhead = cur; //临时头结点
        while(cur.next !=null){
            ListNode cur2  =     cur.next;

            cur.next = cur.next.next;

            cur2.next =curhead;

            curhead =cur2;
        }
        return curhead;
        }*/

        //思想2：
        //将头结点所连接的节点一个个地断开，再重新链接
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curN = cur.next; //将下一个节点的地址先保存起来
            cur.next = head; //本节点指向头结点
            head = cur;
            cur = curN;
        }
        return head;
    }
   //第三道题：返回链表的中间节点：
   /*class Solution {
       public ListNode middleNode(ListNode head) {
           //思想1 ： 先获取链表中节点的个数，然后/2
        /*   if (head == null) {
               return null;
           }
           ListNode cur = head;
           int count = 0;

    //这样设计还需要计算链表的长度
           while (cur != null) {
               cur= cur.next;
               count++;
           }
           int index = count/2;
           ListNode cur2 = head;
           while(index>0){
               cur2 = cur2.next;
               index--;
           }
           return cur2;
       }*/
      //思想2 :
           //由同样的路径，当其速度与时间成反比的思想，当全速度走完路程时，一半的速度走一半的路径。
        /*   if(head ==null){
               return null;
           }
           ListNode fast  = head;
           ListNode slow =head;
           while (fast!=null && fast.next!=null){ //因为不能确定链表的个数是奇数还是偶数
                  fast = fast.next.next;
                  slow = slow.next;
           }
        return slow;
   }*/

//第四道题：
    //返回链表中倒数第k个节点
class Solution4 {
    public int kthToLast(ListNode head, int k) {
        ListNode cur2 = head;
        ListNode cur1 = head;
        //确保指针1领先指针2k个节点
        while(k>0){
            cur1 = cur1.next;
            k--;
        }

            while(cur1!=null){
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur2.val;
    }
}
//第五题：将两个升序链表合并成一个升序链表并返回
class Solution5 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //创建一个新的头结点
        ListNode newhead = null;
        //创建cur指针来保存新链表中的最后一个节点的地址
        ListNode cur = newhead;
//需要依次比较两个节点
        //在编写代码，实现具体的逻辑时，不可能一次性想出所有的逻辑，该怎么解决，——方法1：逐步的编写，因为人的思维有局限性

        while(list1 !=null &&list2!=null){
            if(list1.val <= list2.val){
                cur = list1;
                list1 = list1.next;
                cur =cur.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }

        //当退出循环时，一定会有剩余的节点,且剩余的节点是有序的
        if(list1!=null){
            cur.next = list1;
        }
        if(list2!=null){
            cur.next = list2;
        }

        return newhead;

    }
}

//第六题：
// 以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return null;
        }
        // write code here
        ListNode list1 = new ListNode(-1);
        ListNode list2 = new ListNode(-1);
        ListNode newHead1 = list1;
        ListNode newHead2 = list2;
        ListNode cur = pHead; //创建临时指针
        //需要第一个链表的首节点，尾节点，需要第二个节点的首节点

        while (cur != null) {
            if (cur.val < x) {
                list1.next = cur;  //此种算法解决了next不可控的问题
                list1 = list1.next; //list1最后指向的节点为cur
                cur = cur.next;
            } else {
                list2.next = cur;
                list2 = list2.next;//list2最后指向的节点为cur
                cur = cur.next;
            }
        }
        //当遍历结束后：
        //将后一个链表最后一个节点的next指针置为空
        list2.next = null;
        list1.next = newHead2.next; //将前一个链表的尾结点与后一个链表的有效头结点连接起来
        return newHead1.next;
        //我们在打印链表时，会自动打印下一个节点，所以需要将最后的节点的next指针置为空
    }
}
//第七题：链表的回文结构：
    //判断一个链表是否是回文，且不能够使用数组
    //首先找到中间节点
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        ListNode fast = A;
        ListNode slow = A;
        //先找到中间节点
        while(fast!=null &&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //slow指向的节点为中间节点
        //将中间节点后的链表逆转
        ListNode middle =slow;
        ListNode cur = slow.next;
        slow.next = null;
        while(cur!=null){
            ListNode curN =cur.next;
            cur.next = slow; //直接指向中间节点
            //将slow节点与cur节点均往后移动一位
            slow = cur;
            cur = curN;
        }
//在完成后半部分链表的逆转后，开始判断是否是回文结构
        ListNode first = A;
        ListNode end = cur;
        while(first != middle ){
            if(first.val!=slow.val){
                return false;
            }
            //应该从图形中去发现规律
            if(first.next == middle){
                return true ;
            }

            first = first.next;
            slow = slow.next;
        }
        return true;
    }}
//题目8 ：找到两个单链表的交点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //找出两个链表中相交的节点，不是值相同的节点
        ListNode cur1 = headA;
        // 思想1：找到相交的节点即在一个链表中出现的节点，在另一个节点中也有，一个节点一个节点的遍历
        while(cur1!=null){
            ListNode curN = headB;
            while(curN!=null){
                if(curN == cur1){
                    return cur1;
                }
                curN = curN.next;
            }
            cur1 = cur1.next;

        }
        return  null;
    }
}
 //   思想2：对于两个链表不等长的问题，可以使得长的链表先走一步，然后再进行同步判断

//题目9，给定一个链表，判断链表是否有环？
    //根据两个指针走，一个走两步，一个走一步，如果两者能够相遇，说明此链表是有环的


























































    public class Test {

        public static void main2(String[] args) {
            //关于几种Oj题目：
            //重新做一遍：
            // 1.给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
            //代码实现：


        }


        public static void main1(String[] args) {
            //生成一个单链表

            MySingleList mySingleList = new MySingleList();
            mySingleList.addLast(1);
            mySingleList.addLast(2);
            mySingleList.addLast(6);
            mySingleList.addLast(3);
            mySingleList.addLast(4);
            mySingleList.addLast(5);
            mySingleList.addLast(6);
            mySingleList.display();
            System.out.println();
            mySingleList.removeAllkey(6);
            mySingleList.display();

        }
    }
}